859C - Pie Rules - CodeForces Solution

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int INF = 1e18;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    vector<int> v(n);

    for(int i = 0; i < n; i++) {
        cin >> v[i];
    }

    int total = 0;

    // given a starting position i, what is the max value 
    // the starting player can guarantee
    vector<int> dp(n+1, 0);
    for(int i = n-1; i >= 0; i--) {
        total += v[i];
        // dp[i+1] -> player chooses to take the slice and 
        // other player becomes the starting player in rest 
        // of the game
        //
        // total - dp[i+1] -> player chooses to give away the slice
        // and keep the decoder token, now this player is the starting
        // player in the rest of the game
        dp[i] = max(dp[i+1], total - dp[i+1]);
    }

    cout << total - dp[0] << ' ' << dp[0] << '\n';

    return 0;
}